Dynamically-typed programming languages (such as the MATLAB® programming language) provide a powerful prototyping and development mechanism for programmers. Because such programming languages allow variables to take on the types of expressions that are assigned to them during program execution, programmers do not have to worry about details such as declaring the variable types or creating functions specific for a given variable type. Such languages support a programming style where programmers create (or in some cases, recreate) variables based on local contexts. Variables are frequently used in several different ways and for several different purposes because programmers basically just create variables as they need them.
While dynamically-typed languages support a relaxed programming style for programmers, they present significant challenges for the programming tools that support them. In particular, the most obvious methods for executing dynamically-typed languages provide extremely slow execution speeds. The result is that programmers cannot develop large applications in a dynamically-typed language because a program of any significant size requires too much time to run. The key to making dynamically-typed languages useful is optimizing their execution performance, increasing their execution speed and thereby decreasing the time required to execute programs of any significant size. The technology behind such execution improvement is commonly called “code optimization”, and the tool used to effect those improvements is commonly called a “code optimizer” or just “optimizer”.
Optimizers work by “statically” analyzing a program prior to its execution (or its “run-time”) to predict how the program will behave when executed on input data. Using those predictions, optimizers change the code that is executed so as to minimize the run time required to perform the calculation. In a very simplistic example, an optimizer will analyze a program that always computes and prints “7*6”, and realize that the program will always print “42”. In such a case, the optimizer will remove all instructions used in the computation, and leave in only the instructions required to print “42”. The effectiveness of an optimizer depends on its ability to predict, prior to program execution, how a program will behave when it executes.
Dynamically-typed languages present a significant challenge for optimizers, since by their very nature dynamically-typed languages hide information until execution time. Since the optimizer has less information prior to execution about how a program behaves when it executes, the optimizer is less able to statically predict program behavior and is thereby limited in its ability to improve program execution.
The most significant hindrance in dynamically-typed languages is the inability to statically distinguish between function calls and array accesses. In many programming languages, function calls are distinguished syntactically by the appearance of parentheses; e.g. a function call in the source is indicated by “function_name (arg1, arg2, . . . )”. Parentheses are also commonly used to indicate array accesses (or memory accesses) in languages; e.g. an array access in the source is indicated by “array_name (subscript 1, subscript 2, . . . )” Statically-typed languages are able to easily distinguish between these different uses from variable declarations. The programmer has to provide extra information about the variables to the compilation tool, which allows the tool to determine whether a given usage is an array access or a function call. In dynamically-typed languages, however, where variables can change type during the execution of a single assignment statement, such hints are not readily available. For instance, the variable “x” can be used as a function call in one statement of a program in the form “x(1,1)”, then be used as an array access two statements later in the same form: “x(1,1)”. Users cannot always easily determine whether a given reference is a function call or array access, making it difficult for them to provide hints to a compilation tool.
A programming reference such as “x(1,1)” above which may be either a function call or a memory access when examined from a strictly syntactic analysis is known as an “ambiguous reference” and the variable associated with that reference (“x” in the example) is known as an “ambiguous name”. “Function calls” are variable references that when executed in the interpreter cause the program counter of the computer to jump to a non-sequential location, execute some number of instructions, then jump back to the next sequential instruction (accounting for “branch slots”) following the function call. An “array access” is a reference to a variable that represents a collection of elements; the access may either fetch or set the values for some number of that collection. A “scalar access” is a reference to a variable that represents one element, and the access may either fetch or set the value of that element. “Memory access” refers to either an array access or scalar access, particularly when the collective nature of the variable is unknown. If a programming reference is used as a function call along some execution paths and as a memory access along other execution paths, the reference is considered a “dual usage”.
The MATLAB® programming language (as defined by the MATLAB interpreter version 13.1) is one example of a dynamically-typed language. It not only supports parentheses as the syntactic notation for both function calls and array accesses, but it also requires that a function that takes no arguments be called without following parentheses. This means that a simple variable access (in MATLAB, such a reference can be either scalar or vector) is ambiguous with function calls. This ambiguity greatly increases the difficulty of building effective programming tools for the language.
The MATLAB programming language is defined by the actions of the interpreter provided for the language by The MathWorks, Inc. Interpreters are useful programming tools for dynamically-typed languages, in that they provide a mechanism naturally suited for resolving typing questions during execution. Interpreters create and maintain an execution state environment (such as a symbol table) while they dynamically execute a program. This environment allows an interpreter at any point during execution to examine the state of the program, including the values and types that have been assigned to variables. This environment allows an interpreter to easily resolve any ambiguity between array accesses and function calls, because it can determine precisely the characteristics of the variable in question. The following paragraph (from “MATLAB: The Language of Technical Computing—Using MATLAB Version 6”, The MathWorks, Inc., 2002. p. 16-13) describes how MATLAB resolves variables as it executes:
“When MATLAB comes upon a new name, it resolves it into a specific function by following these steps:                1 Checks to see if the name is a variable.        2 Checks to see if the name is a subfunction, a MATLAB function that resides in the same M-file as the calling function. . . .        3 Checks to see if the name is a private function, a MATLAB function that resides in a private directory accessible only to M-files in the directory immediately above it. . . .        4 Checks to see if the name is a function on the MATLAB search path. MATLAB uses the first file it encounters with the specified name”        
Once MATLAB has identified a name as a function rather than as a variable, it resolves the function using the following algorithm (“MATLAB: The Language of Technical Computing—Using MATLAB Version 6”, The MathWorks, Inc., 2002. pp. 21-67 and 21-68):
“Function Precedence Order
The function precedence order determines the precedence of one function over another based on the type of function and its location on the MATLAB path. From the perspective of method selection, MATLAB contains two types of functions: those built into MATLAB, and those written as M-files. MATLAB treats these types differently when determining the function precedence order.
MATLAB selects the correct function for a given context by applying the following function precedence rules, in the order given.
For built-in functions:
1) Overloaded Methods
If there is a method in the class directory of the dispatching argument that has the same name as a MATLAB built-in function, then this method is called instead of the built-in function.
2) Nonoverloaded MATLAB Functions
If there is no overloaded method, then the MATLAB built-in function is called. MATLAB built-in functions take precedence over both subfunctions and private functions. Therefore, subfunctions or private functions with the same name as MATLAB built-in functions can never be called.
For nonbuilt-in functions:
1) Subfunctions
Subfunctions take precedence over all other M-file functions and overloaded methods that are on the path and have the same name. Even if the function is called with an argument of type matching that of an overloaded method, MATLAB uses the subfunction and ignores the overloaded method.
2) Private Functions
Private functions are called if there is no subfunction of the same name within the current scope. As with subfunctions, even if the function is called with an argument of type matching that of an overloaded method, MATLAB uses the private function and ignores the overloaded method.
3) Class Constructor Functions
Constructor functions (functions having names that are the same as the @directory, for example @polynom/polynom.m) take precedence over other MATLAB functions. Therefore, if you create an M-file called polynom.m and put it on your path before the constructor @polynom/polynom.m version, MATLAB will always call the constructor version.
4) Overloaded Methods
MATLAB calls an overloaded method if it is not masked by a subfunction or private function.
5) Current Directory
A function in the current working directory is selected before one elsewhere on the path.
6) Elsewhere On Path
Finally, a function anywhere else on the path is selected.”
Because the MATLAB interpreter dynamically maintains the program state, it can precisely resolve any ambiguity in the use of a name.
The just-described method for resolving the ambiguous usage of a name in a statement is well-suited for an interpreter, but does not work for a compiler because the compiler must create executable code well before any statements in the program being compiled are executed. Specifically, whether or not a name is defined as a function at the time of execution of a particular statement is unknown ahead of time. Compilers and related tools work by statically predicting the program's execution at run-time. Because they are predicting, and not directly executing, these tools do not have the advantage of a dynamically-maintained execution state.
Resolving the ambiguity, particularly between function calls and array/memory accesses, is an extremely important problem. Since function calls may have widely different effects on a program's state than array accesses, separating them is critical to the success of any program analysis such as optimization. For instance, determining how information flows across procedure calls is an important area of analysis. Such analysis is impossible to perform without knowledge of the procedure calls, which cannot be determined unless procedure calls, memory accesses, and dual usages are separated. This type of information, which is typically used to build a call graph of the procedures and analyze across them, is valuable both to compiler tools and to interpreters that want to pre-optimize program performance before initiating execution. This information may also be useful in contexts other than building a call graph, such as when performing localized procedure inlining.
Because of the significance of the problem, much research has been performed on the problem of statically distinguishing among function calls, array/memory accesses, and dual usage in ambiguous dynamically-typed languages. De Rose and Padua (De Rose, Luiz, and Padua, David, “Techniques for the Translation of MATLAB Programs into Fortran 90”, ACM Transactions on Programming Languages and Systems, Vol 21, No. 2, March, 1999. Pages 286-323) developed a state transition diagram to be used with a simple walk over the program representation to distinguish function calls, array accesses, and dual usages. This approach suffers from two deficiencies: a) it does not take advantage of control flow, and b) it does not account for the fact that a dynamically-typed language may have multiple variables that share the same name. The first deficiency will cause the approach to incorrectly label some cases of dual usage. The second deficiency will cause the approach to label as dual usages many variables that are not. In particular, since dynamically-typed languages allow variables to be created and destroyed as values are assigned to them, it is very feasible for a variable to be a function call in the first part of a program and an array access in the later part—in essence, being two completely different variables. De Rose and Padua's technique will force the two variables into one, causing a false dual usage. A compiler transformation “variable renaming” eliminates this false usage when utilized in the embodiment of this invention.
Almasi and Padua developed a different approach based on a data flow analysis framework in a 2002 paper (Almasi, George and Padua, David, “MaJIC: Compiling MATLAB for Speed and Responsiveness”, ACM Conference on Programming Language Design and Implementation, June, 2002, Pages 294-303). Their approach is based on a dataflow analysis approach using the fact that “a symbol that has a reaching definition as a variable on all paths leading to it MUST be a variable” (emphasis added). They incorporate this fact into a meet-over-all-paths data analysis framework by defining for each statement a set s of symbols which are known to be variables at that statement. The set s can then be computed for every statement by any number of well-known techniques for computing fixed-point solutions in a lattice. A similar, but different, meet-over-all-paths analysis framework can be set up to determine that set of variables at each statement that are known to be function calls.
Almasi and Padua's approach provides significantly more precision than De Rose and Padua's approach, but still suffers from two significant disadvantages. First, different approaches are required to compute variables and function calls: the computations, while similar, cannot be performed simultaneously on the same data. This means that computing both the variables and the function calls requires roughly twice the amount of some resource (a skilled practitioner will realize that time and memory can be traded off in programmed computers, so that computing both requires roughly either twice the memory or twice the computation time of computing either alone). Since it is necessary to compute both in order to compute “dual usage” variables, this extra overhead is required for most programs. Second, in addition to neither approach (that is, to computing function calls and variable accesses) being able to solve the other problem, neither approach can be applied to other data flow problems, such as dead code elimination, constant propagation, or variable renaming. These transformations are data flow analysis problems that are commonly used by compilers and interpreters to improve program execution. Since they require a different dataflow lattice than that used by Almasi and Padua, an optimizer that attempts both Almasi and Padua's approach and common optimization transformations will incur even more computational overhead.
A problem similar to that of inferring function calls in ambiguous, dynamically-typed languages is the problem of detecting uninitialized variables in statically-typed languages such as FORTRAN. U.S. Pat. No. 5,615,369 granted to Holler on Mar. 25, 1997, which is incorporated by reference, specifies an invention for detecting and initializing uninitialized variables in FORTRAN. Holler's framework computes over all paths whether it is possible for the use of a variable to reach back to the entry of a program without passing through a definition of that variable. If so, the variable may be uninitialized when used, and the invention inserts an initialization at the source. Holler's method provides the same dataflow lattice that is used in more conventional optimization problems, allowing it to be reused for other transformations. However, Holler's approach computes information over all possible control flow paths, causing it to be expensive to compute in some instances.
Dataflow analysis frameworks, lattices, and techniques are well known in the art and are discussed fully in Chapter 4 of a book by Allen, Randy and Kennedy, Ken entitled “Optimizing Compilers for Modern Architectures”, Morgan Kaufmann publishers, 2002. This chapter is incorporated by reference herein in its entirety. The goal of dataflow analysis is to relate each “use” of a variable in the program (where “use” means any programming construct that may read or in any other way use the value that the variable contains in the computer's memory) to all possible “definitions” of that variable in the program (where “definition” means any programming construct that may set or change the value that the variable contains in the computer's memory) that can possibly set the value that the use may receive. “Definitions” are also commonly called “defs”. A “reference” (or “ref”) is any form of reference to a variable, either a use of the variable or a definition of the variable
It is well known in the art how to go from a definition of a variable to all locations in a computer program that may use the definition at execution time. Specifically, a “definition-use chain” is a data structure that is commonly used to perform such an operation. A definition-use chain is comprised of nodes and edges, where nodes represent variable references in the user's program, and an edge exists between two nodes when one node is a definition whose value may be used by the second node. In other words, an edge connects a definition to all possible runtime uses of that definition. While edges are normally indicated as going from definition to use, following the flow of data within the program, they may be as easily thought of as flowing from use to def (indicating a use that needs a value defined by the def), and a skilled artisan can easily construct data structures that allow both forms to be used. Note that the term “definition use graph” is more appropriate than the traditional “definition-use chains” because “graph” more correctly characterizes the nature of the information the data structure contains. The definition-use chain (or graph) is essentially a scalar version of true dependences within a program. Note that each node in a definition use graph is also referred to as a “permanent node” if the node represents a permanent definition (e.g. represents a statement or represents a variable) originally present in the user's computer program. In contrast if a node represents a temporary definition that is added automatically (for all variables in most embodiments) then the node is called a “temporary node”. As noted below, a temporary node becomes a permanent node in some embodiments during optimization if a variable in the user's computer program was originally undefined.
Constructing definition-use edges within a single straight-line block of code is well known. One visits each statement in order in the basic block, noting the variables defined by each statement as well as the variables used by each statement. For each use, an edge is added to the definition use graph for that use back to the last exposed definition in the block of that variable—in other words, to every definition that reaches the use. Whenever a new definition is encountered for a variable, the new definition kills (i.e. over-writes) the existing definition, so that later uses are linked only to the new definition, not to the old. When the end of the block is reached, the definition use graph is complete.
Constructing a definition-use graph across a program comprised of more than a single straight-line block of code is more complicated. Standard art contains many different methods for computing definition-use graphs for programs containing control flow, many of which are summarized in Chapter 1 by Kennedy, Ken entitled “A survey of data-flow analysis techniques”, In a book by S. S. Muchnick and N. D. Jones, editors, “Program Flow Analysis: Theory and Applications,”, pp. 1-51. Prentice Hall publishers, 1981. At a high level, the methods all work by decomposing a program into simpler units (basic blocks, intervals, or others) and a control flow graph indicating the flow between the units. In a local pass, information is computed for each individual unit, regardless of the control flow among the units. Such information typically consists of sets of variables that are used, defined, killed (“kills” are definitions where all existing values in a variable can safely be assumed to be replaced), and reaches (“reaches” are definitions that can reach a given use). This local information is then combined into global information by propagating it along the control flow graph, using any of a number of dataflow propagation techniques (including iterative, interval, parse, and others). After the global information is available for the whole program, a definition-use graph can then be constructed by distributing the information back across the local units.
Dataflow information (e.g. in most embodiments definitions and uses) are propagated by several techniques (i.e. iterative, interval, and so on) are based on framing the problem inside a lattice(also referred to in this patent application as a dataflow framework). A lattice, as defined in S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann, 1997, consists of a set of values and two operations “meet” and “join”, both of which are closed, commutative, associative, distributive (in this patent application, but not in general), and monotonic (again in this patent application, but not in general). A lattice also has two designated elements “top” and “bottom”. All the dataflow propagation techniques discussed at the beginning of this paragraph can be applied to any problem that can be embedded in such a lattice (or dataflow framework). Propagating uses and definitions of variables is certainly one type of information embedded in a lattice in all embodiments of the invention.
When definitions and uses are propagated through a lattice, it is often convenient to abstract the resulting flow of data in a definition-use graph. Definition-use graphs can be embodied in a number of different forms, including linked lists, bit matrices, sets, bit vectors, etc. While the description of the techniques most often refers to a linked list of edges, skilled practitioners will readily recognize that all representations are equivalent in terms of the application of this invention.
One of the reasons that the ability to distinguish function calls from memory accesses is critical to optimizing programs written in a dynamically-typed language is that an understanding of function calls is critical to constructing definition-use graphs and optimizing transformations. A memory access that is only a use (a fact that can be determined from a syntactic analysis of the program in most languages that are not dynamically-typed) is guaranteed not to change the state of memory (other than registers) in a programmed computer. A memory access that is a definition (a fact that can again be determined from a syntactic analysis of the program in most languages that are not dynamically-typed) is guaranteed to change only a limited number of elements of memory of a programmed computer. A function call, however, can execute an arbitrary number of instructions, which may fetch and set any number of elements of a computer's memory. Since the goal of optimization is to predict at compile time what a program is going to do at run time, function calls are a large source of unpredictability, and thus are difficult for optimization techniques to handle. Memory accesses, on the other hand, have a limited set of effects, and are much more easily handled. As a result, separating function calls from memory accesses is critical to effectively optimizing a program, and in particular to constructing an accurate definition-use graph for a program.
“Entry points” and “entry nodes” are well defined terms in compiler literature. An entry point is a program location by which control may enter a function. In many programming languages, that is a single statement, such as in MATLAB, where the function header is the only entry point. In other languages, such as FORTRAN, multiple entry points into a procedure are supported, and any of those serves as an entry point. For analysis, compilers often simplify programs with multiple entry points by creating one unique entry point and by making the multiple entry points labels. When control reaches the unique entry point, it immediately branches to the appropriate label representing the former entry point to which control was to transfer. An “entry node” is the intermediate representation of the unique entry point.